package hzk.codex2016.sort;

public class QuickSorter implements Sorter {

	public void sort(int[] arr) {
		sort(arr,0,arr.length-1);
	}
	
	
	void sort(int[] a,int lo,int hi){
		
		System.out.printf("%d,%d\n",lo,hi);
		if (lo>=hi) return;
		int i=lo+1,j=hi,tmp;
		//i--;j++;
		int v=a[lo];
		while(true){			
			for (;i<hi && a[i]<v;i++);
			for (;j!=lo && a[j]>v;j--);
			if (i<j){
				tmp=a[i];a[i]=a[j];a[j]=tmp;
			}else{
				break;
			}
		}
		a[lo]=a[j];a[j]=v;
		sort(a,lo,j-1);
		sort(a,j+1,hi);
		
		
		
	}
	/**
	 * 3-way quick sort
	 * @param a
	 * @param lo
	 * @param hi
	 */
	void sort3(int[] a,int lo,int hi){
		if (lo>=hi) return;
		int lt=lo,i=lo+1,gt=hi,tmp;
		int v=a[lo],d;
		while (i<=gt){
			d=a[i]-v;
			if (d==0){
				i++;
			}else if (d<0){
			 
				a[lt++]=a[i];
				a[i++]=v;
			}else {
				tmp=a[gt];
				a[gt--]=a[i];
				a[i]=tmp;
			}
		}
		
		sort3(a,lo,lt-1);
		sort3(a,gt+1,hi);
		
		
		
		
	}

	public static void main(String[] args) {
		Sorter s = new QuickSorter();

		for (int i = 1; i < 10; i++) {
			//Arrs.test(s, i);
		}
		for (int i = 100; i < 1e5; i *= 10) {
			Arrs.test(s, 100);
		}
		
		for (int i = 100; i < 1e5; i *= 10) {
			Arrs.test(s, i);
		}
		for (int i = 1; i <= 5; i++) {
			Arrs.test(s, 1010000,300);
		}
		for (int i = 1; i <= 5; i++) {			
			//Arrs.testJdkArrays(1010000,300);
		}
	}

}
